package com.huangkailong.leetcode;

import java.util.Objects;

/**
 * <h1>两数相加</h1>
 *
 * 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。<br/>
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。<br/>
 * 你可以假设除了数字 0 之外，这两个数都不会以 0开头。<br/>
 *
 * 示例 1：<br/>
 * 输入：l1 = [2,4,3], l2 = [5,6,4]<br/>
 * 输出：[7,0,8]<br/>
 * 解释：342 + 465 = 807.<br/>
 *
 * 示例 2：<br/>
 * 输入：l1 = [0], l2 = [0]<br/>
 * 输出：[0]<br/>
 *
 * 示例 3：<br/>
 * 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]<br/>
 * 输出：[8,9,9,9,0,0,0,1]<br/>
 *
 * 提示：<br/>
 * 每个链表中的节点数在范围 [1, 100] 内<br/>
 * 0 <= Node.val <= 9<br/>
 * 题目数据保证列表表示的数字不含前导零<br/>
 * 
 * @author huangkl
 * @date 2021-04-25 13:18
 */
public class TwoNumbersAdd {

    /**
     * 模拟计算方式进行运行
     */
    public static ListNode solution1(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode tmpL1 = l1;
        ListNode tmpL2 = l2;
        ListNode tmpRet = null;
        ListNode ret = null;
        while (Objects.nonNull(tmpL1) && Objects.nonNull(tmpL2)){
            if(Objects.isNull(tmpRet)){
              ret = tmpRet = new ListNode();
            }else if(Objects.isNull(tmpRet.next)){
              tmpRet.next = new ListNode();
              tmpRet = tmpRet.next;
            }

            int sum = tmpL1.val + tmpL2.val + carry;
            tmpRet.val = sum%10;
            carry = sum/10;
            tmpL1 = tmpL1.next;
            tmpL2 = tmpL2.next;
        }

        while (Objects.nonNull(tmpL1)){
            tmpRet.next = new ListNode();
            tmpRet = tmpRet.next;

            int sum = tmpL1.val + carry;
            tmpRet.val = sum%10;
            carry = sum/10;
            tmpL1 = tmpL1.next;
        }

        while (Objects.nonNull(tmpL2)){
            tmpRet.next = new ListNode();
            tmpRet = tmpRet.next;

            int sum = tmpL2.val + carry;
            tmpRet.val = sum%10;
            carry = sum/10;
            tmpL2 = tmpL2.next;
        }

        if(carry > 0){
            tmpRet.next = new ListNode();
            tmpRet = tmpRet.next;
            tmpRet.val = carry;
        }
        return ret;
    }

    /**
     * solution1 代码精简
     */
    public static ListNode solution2(ListNode l1, ListNode l2) {
        int carry = 0;
        ListNode tmpL1 = l1;
        ListNode tmpL2 = l2;
        ListNode tmpRet = null;
        ListNode ret = null;
        while (Objects.nonNull(tmpL1) || Objects.nonNull(tmpL2)){
            if(Objects.isNull(tmpRet)){
                ret = tmpRet = new ListNode();
            }else if(Objects.isNull(tmpRet.next)){
                tmpRet.next = new ListNode();
                tmpRet = tmpRet.next;
            }

            int sum;
            if(Objects.nonNull(tmpL1) && Objects.nonNull(tmpL2)){
                sum = tmpL1.val + tmpL2.val + carry;
                tmpL1 = tmpL1.next;
                tmpL2 = tmpL2.next;
            }else if(Objects.isNull(tmpL1)){
                sum = tmpL2.val + carry;
                tmpL2 = tmpL2.next;
            }else {
                sum = tmpL1.val+ carry;
                tmpL1 = tmpL1.next;
            }

            tmpRet.val = sum%10;
            carry = sum/10;
        }

        if(carry > 0){
            tmpRet.next = new ListNode();
            tmpRet = tmpRet.next;
            tmpRet.val = carry;
        }
        return ret;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }
